#include <iostream>
#include <vector>
#include <functional>
#include <stdexcept>

/**
 * @brief 自定义优先级队列实现
 * @tparam T 元素类型
 * @tparam Compare 比较函数类型，默认为最大堆
 */
template<typename T, typename Compare = std::less<T>>
class PriorityQueue {
private:
    std::vector<T> heap;      // 使用vector存储堆元素
    Compare comp;             // 比较函数对象
    
    /**
     * @brief 获取父节点索引
     * @param index 当前节点索引
     * @return 父节点索引
     */
    size_t parent(size_t index) const {
        return (index - 1) / 2;
    }
    
    /**
     * @brief 获取左子节点索引
     * @param index 当前节点索引
     * @return 左子节点索引
     */
    size_t leftChild(size_t index) const {
        return 2 * index + 1;
    }
    
    /**
     * @brief 获取右子节点索引
     * @param index 当前节点索引
     * @return 右子节点索引
     */
    size_t rightChild(size_t index) const {
        return 2 * index + 2;
    }
    
    /**
     * @brief 上浮操作（堆化向上）
     * 将新插入的元素调整到正确位置，保持堆性质
     * @param index 需要上浮的节点索引
     */
    void heapifyUp(size_t index) {
        // 如果到达根节点或者满足堆性质，则停止
        while (index > 0) {
            size_t parentIdx = parent(index);
            
            // 如果当前节点比父节点"优先级更高"（根据比较函数），则交换
            if (comp(heap[parentIdx], heap[index])) {
                std::swap(heap[parentIdx], heap[index]);
                index = parentIdx;  // 继续向上检查
            } else {
                break;  // 堆性质已满足
            }
        }
    }
    
    /**
     * @brief 下沉操作（堆化向下）
     * 将根节点（删除后）或不符合堆性质的节点调整到正确位置
     * @param index 需要下沉的节点索引
     */
    void heapifyDown(size_t index) {
        size_t size = heap.size();
        
        while (true) {
            size_t leftIdx = leftChild(index);
            size_t rightIdx = rightChild(index);
            size_t largest = index;  // 假设当前节点是最大的
            
            // 比较左子节点和当前节点
            if (leftIdx < size && comp(heap[largest], heap[leftIdx])) {
                largest = leftIdx;
            }
            
            // 比较右子节点和当前最大节点
            if (rightIdx < size && comp(heap[largest], heap[rightIdx])) {
                largest = rightIdx;
            }
            
            // 如果当前节点不是最大的，需要交换并继续下沉
            if (largest != index) {
                std::swap(heap[index], heap[largest]);
                index = largest;  // 继续向下检查
            } else {
                break;  // 堆性质已满足
            }
        }
    }

public:
    /**
     * @brief 默认构造函数
     */
    PriorityQueue() = default;
    
    /**
     * @brief 使用迭代器范围构造优先级队列
     * @tparam InputIt 输入迭代器类型
     * @param first 起始迭代器
     * @param last 结束迭代器
     */
    template<typename InputIt>
    PriorityQueue(InputIt first, InputIt last) : heap(first, last) {
        // 构建堆：从最后一个非叶子节点开始向前进行下沉操作
        // 时间复杂度O(n)，比逐个插入的O(nlogn)更优
        for (int i = (heap.size() / 2) - 1; i >= 0; --i) {
            heapifyDown(i);
        }
    }
    
    /**
     * @brief 检查队列是否为空
     * @return true如果队列为空
     */
    bool empty() const {
        return heap.empty();
    }
    
    /**
     * @brief 返回队列中元素数量
     * @return 元素数量
     */
    size_t size() const {
        return heap.size();
    }
    
    /**
     * @brief 返回优先级最高的元素（堆顶元素）
     * @return 常量引用到堆顶元素
     * @throw std::out_of_range 如果队列为空
     */
    const T& top() const {
        if (empty()) {
            throw std::out_of_range("PriorityQueue is empty");
        }
        return heap[0];
    }
    
    /**
     * @brief 插入新元素
     * @param value 要插入的值
     */
    void push(const T& value) {
        // 1. 将新元素添加到堆的末尾
        heap.push_back(value);
        
        // 2. 上浮新元素到正确位置，恢复堆性质
        heapifyUp(heap.size() - 1);
    }
    
    /**
     * @brief 移动插入新元素
     * @param value 要插入的值（右值引用）
     */
    void push(T&& value) {
        // 1. 将新元素移动到堆的末尾
        heap.push_back(std::move(value));
        
        // 2. 上浮新元素到正确位置
        heapifyUp(heap.size() - 1);
    }
    
    /**
     * @brief 删除优先级最高的元素
     * @throw std::out_of_range 如果队列为空
     */
    void pop() {
        if (empty()) {
            throw std::out_of_range("PriorityQueue is empty");
        }
        
        // 1. 将堆顶元素与最后一个元素交换
        std::swap(heap[0], heap[heap.size() - 1]);
        
        // 2. 删除原来的堆顶元素（现在在末尾）
        heap.pop_back();
        
        // 3. 对新的堆顶元素进行下沉操作，恢复堆性质
        if (!empty()) {
            heapifyDown(0);
        }
    }
    
    /**
     * @brief 打印堆内容（用于调试）
     */
    void print() const {
        std::cout << "Heap: ";
        for (const auto& item : heap) {
            std::cout << item << " ";
        }
        std::cout << std::endl;
    }
};

// 示例使用和测试
int main() {
    std::cout << "=== 最大堆测试（默认）===" << std::endl;
    PriorityQueue<int> maxHeap;
    
    // 插入元素
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(4);
    maxHeap.push(1);
    maxHeap.push(5);
    maxHeap.push(9);
    
    std::cout << "堆大小: " << maxHeap.size() << std::endl;
    maxHeap.print();
    
    std::cout << "出队顺序: ";
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    std::cout << std::endl;
    
    std::cout << "\n=== 最小堆测试 ===" << std::endl;
    // 使用std::greater创建最小堆
    PriorityQueue<int, std::greater<int>> minHeap;
    
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(1);
    minHeap.push(5);
    minHeap.push(9);
    
    std::cout << "出队顺序: ";
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }
    std::cout << std::endl;
    
    std::cout << "\n=== 批量构造测试 ===" << std::endl;
    std::vector<int> data = {7, 2, 8, 1, 6};
    PriorityQueue<int> batchHeap(data.begin(), data.end());
    
    std::cout << "批量构造后的堆: ";
    batchHeap.print();
    
    return 0;
}